'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-10-27 20:44:21
'''
#
# @lc app=leetcode.cn id=123 lang=python3
#
# [123] 买卖股票的最佳时机 III
#

# @lc code=start
from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[i][j][k] 第i天交易已交易j次且出在k状态，k=0表示卖出，k=1表示买入
        dp = [[0]*2 for _ in range(3)]
        dp[0][0]=0
        dp[0][1]=0-prices[0]
        # dp[0][1][0]=0
        dp[1][1]=0-prices[0]
        # dp[0][2][0]=0
        dp[2][1]=0-prices[0]
        # 后面的两组赋值是什么意思？
        for i in range(1, len(prices)):
            v = prices[i]
            dp[0][0] = dp[0][0]
            dp[0][1] = max(dp[0][1], dp[0][0]-v)
            dp[1][0] = max(dp[1][0], dp[0][1]+v)
            dp[1][1] = max(dp[1][1], dp[1][0]-v)
            dp[2][0] = max(dp[2][0], dp[1][1]+v)
        ans = []
        for i in range(3):
            ans.extend(dp[i])
        return max(ans)

# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    prices = [3,3,5,0,0,3,1,4]
    print(solution.maxProfit(prices))


